[Coding041] LeetCode 20

Valid Parentheses

More coding records

Get the knowledge flowing and circulating! :)

目录

※ 本题收获

• switch的用法；

• 对于栈的操作，如果想要出栈，则需要先判断栈是否为空。如果栈是空的，则stack.pop(); stack.peek();都是会报错的。

心得：一开始在看这道题的时候，时隔很久了。突然间竟然没了思路。后来慢慢调试，写出了代码1.

就代码2~4而言，都是之前自己写过的，却未曾想到现在竟然都不记得了！

所以说啊，编程这东西，同一道题（哪怕像本题是easy），依然值得反复再看、再编，直到把思路融汇贯通。

看着自己的代码1，显得十分生涩。但是最终调试成功，也是值得开心的。

本题收获还是比较大的。比如这个用栈来实现括号匹配的思路：

★ 普通思路：

1. 首先对于左一半，都要入栈；

2. 对于由一半，都要比较：如果和上一个入栈的匹配了，例如上一个入栈的是{，而当前是}，则证明可以把上一个刚刚入栈的{给弹出来，继而继续处理下一个字符；

3. 要知道，不管怎样入栈和出栈，都会遇到这样的情况：({[]})[] or ([{}])，即，总有两个字符刚好是左右匹配的括号；这样的话，就可以遇到匹配的，就弹出，最后留下空栈。

★ 好思路：

1. 看到左括号({[，则对应入栈右括号)}]；

2. 如果看到了右括号，则出栈，看看是否当前处理的字符和栈顶是一样的

   • 不一样，则一定是false了；

题目：20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

xxxxxxxxxx
2
1
Input: s = "()"
2
Output: true

Example 2:

xxxxxxxxxx
2
1
Input: s = "()[]{}"
2
Output: true

Example 3:

xxxxxxxxxx
2
1
Input: s = "(]"
2
Output: false

Constraints:

• 1 <= s.length <= 104

• s consists of parentheses only '()[]{}'.

代码1（配 · 手绘过程图）

xxxxxxxxxx
53
1
class Solution {
2
    public boolean isValid(String s) {
3
        char[] cs = s.toCharArray();
4
        Stack<Character> stack = new Stack();
5
        for (char c : cs)
6
        {
7
            switch(c)
8
            {
9
                case '(':
10
                    stack.push(c);
11
                    break;
12
                case '[':
13
                    stack.push(c);
14
                    break;
15
                case '{':
16
                    stack.push(c);
17
                    break;
18
                
19
                case ')':
20
                    {
21
                        if (!stack.empty() && stack.peek() == '(')
22
                            stack.pop();
23
                        else
24
                            return false;
25
                    }
26
                    break;
27
                case ']':
28
                    {
29
                        if (!stack.empty() && stack.peek() == '[')
30
                            stack.pop();
31
                        else
32
                            return false;
33
                    }
34
                    break;
35
                case '}':
36
                    {
37
                        if (!stack.empty() && stack.peek() == '{' )
38
                            stack.pop();
39
                        else
40
                            return false;
41
                    }
42
                    break;
43

44
            }
45
            
46
        }
47

48
        if (stack.empty())
49
            return true;
50
        else
51
            return false;
52
    }
53
}

复杂度分析

代码2

xxxxxxxxxx
23
1
class Solution {
2
    public boolean isValid(String s) {
3
        
4
        Stack<Character> stack = new Stack<>();
5
        
6
        stack.push('#');
7
        for (int i = 0; i < s.length(); i++)
8
        {
9
            char c = s.charAt(i);
10
            
11
            if (c == ')' && !stack.empty() && stack.peek() == '(')
12
                stack.pop();
13
            else if (c == ']' && !stack.empty() && stack.peek() == '[')
14
                stack.pop();
15
            else if (c == '}' && !stack.empty() && stack.peek() == '{')
16
                stack.pop();
17
            else
18
                stack.push(c);
19
        }
20
        
21
        return stack.peek() == '#';  // 省了判空的步骤了~ 巧妙。
22
    }
23
}

代码3（配 · 手绘过程图）

xxxxxxxxxx
21
1
class Solution {
2
    public boolean isValid(String s) {
3
        
4
        Stack<Character> stack = new Stack<>();
5
        
6
        for (char c : s.toCharArray())
7
        {
8
            if (c == '(')
9
                stack.push(')');
10
            else if (c == '[')
11
                stack.push(']');
12
            else if (c == '{')
13
                stack.push('}');
14
            else if (stack.empty() || stack.pop() != c)
15
                return false;
16
                           
17
        }
18
        
19
        return stack.empty();
20
    }
21
}

代码4（配 · 手绘过程图）

思路：使用数组来代替栈！

xxxxxxxxxx
32
1
class Solution {
2
    public boolean isValid(String s) {        
3
        // 使用数组替代栈（array → stack）
4
        char [] stack = new char[s.length()];
5
        int head = -1;
6
        
7
        for (char c : s.toCharArray())
8
        {
9
            switch(c)
10
            {
11
                case '(': 
12
                    head = head + 1;
13
                    stack[head] = ')';
14
                    break;
15
                case '[':
16
                    head = head + 1;
17
                    stack[head] = ']';
18
                    break;
19
                case '{':
20
                    head = head + 1;
21
                    stack[head] = '}';
22
                    break;
23
                    
24
                default:
25
                    if (head == -1 || stack[head--] != c)
26
                        return false;
27
            }
28
        }
29
        
30
        return head == -1;
31
    }
32
}

测试样例

• "(]"

  • false

• "(])"

  • false

• "()[]{}"

  • true

• "([])[]{}"

  • true

• "]"

  • false

• "({})[(])"

  • false

★ 知识点积累 (Java)

• switch-case使用方法

  • case后面跟的是判断表达式；

  • 每个case体里要有break，否则会顺序往下执行；

  • case执行完后，会执行switch体外的语句。

xxxxxxxxxx
29
1
public class xxx {
2

3
    public static void main(String[] args) {
4
        // TODO Auto-generated method stub
5

6
        int option = 2;
7

8
        switch (option) 
9
        {
10

11
            case 1:
12
                System.out.println("选择了选项 1");
13
                break;
14

15
            case 2:
16
                System.out.println("选择了选项 2");
17
                break;
18

19
            case 3:
20
                System.out.println("选择了选项 3");
21
                break;
22

23
            default:
24
                System.out.println("无效选项");
25
                break;
26

27
        }
28
    }
29
}

运行结果：

xxxxxxxxxx
29
1
public class xxx {
2

3
    public static void main(String[] args) {
4
        // TODO Auto-generated method stub
5

6
        int option = 2;
7

8
        switch (option) 
9
        {
10
            case 1:
11
                System.out.println("选择了选项 1");
12
                break;
13
    
14
            case 2:
15
                System.out.println("选择了选项 2");
16
                // break;
17
    
18
            case 3:
19
                System.out.println("选择了选项 3");
20
                break;
21
    
22
            default:
23
                System.out.println("无效选项");
24
                break;
25
        }
26
        
27
        System.out.println("Outside Switch!");
28
    }
29
}

运行结果：

xxxxxxxxxx
29
1
public class xxx {
2

3
    public static void main(String[] args) {
4
        // TODO Auto-generated method stub
5

6
        int option = 100;
7

8
        switch (option) 
9
        {
10
            case 1:
11
                System.out.println("选择了选项 1");
12
                break;
13
    
14
            case 2:
15
                System.out.println("选择了选项 2");
16
                // break;
17
    
18
            case 3:
19
                System.out.println("选择了选项 3");
20
                break;
21
    
22
            default:
23
                System.out.println("无效选项");
24
                break;
25
        }
26
        
27
        System.out.println("Outside Switch!");
28
    }
29
}

运行结果：